package com.fanco.learn_datastruct_leetcode.leetcode;

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
 * 数字与字母的映射规则参考  手机键盘的映射规则
 *
 * @author qiaowang 2021/7/6
 */
public class Day10 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String digits = "23";
        System.out.println(solution.letterCombinations(digits));

    }

    private static class Solution {
        public List<String> letterCombinations(String digits) {
            List<String> combinations = new ArrayList<>();
            // 不传任何数字时，返回一个空的列表
            if (digits.length() == 0) {
                return combinations;
            }

            Map<Character, String> map = new HashMap<Character, String>(8) {
                {
                    put('2', "abc");
                    put('3', "def");
                    put('4', "ghi");
                    put('5', "jkl");
                    put('6', "mno");
                    put('7', "pqrs");
                    put('8', "tuv");
                    put('9', "wxyz");
                }
            };
            // 定义一个深度指针，但深度与digits长度一样时，将当前这条路径存在list中
            backTrackCombinations(combinations, map, digits, 0, new StringBuffer());
            return combinations;
        }

        private void backTrackCombinations(List<String> combinations, Map<Character, String> map, String digits, int index, StringBuffer combination) {
            if (index == digits.length()) {
                combinations.add(combination.toString());
            } else {
                char c = digits.charAt(index);
                String letters = map.get(c);
                for (int i = 0; i < letters.length(); i++ ) {
                    combination.append(letters.charAt(i));
                    backTrackCombinations(combinations, map, digits, index+1, combination);
                    // 如果不删除字符，combination字符会越来越长。
                    combination.deleteCharAt(index);
                }
            }

        }
    }
}
